package tree;

import java.util.List;

public class Solution {
    /**
     * 二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        list.add(root.val);根

        List<Integer> leftTree = preorderTraversal(root.left);
        list.addAll(leftTree);左

        List<Integer> rightTree = preorderTraversal(root.right);
        list.addAll(rightTree);右

        return list;

    }
     */

    /**
     * p q
     * 时间复杂度：O min(m,n)
     * 判断两棵树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
     if((p == null && q != null) || (p != null && q == null)){//两个节点一个为空另一个不为空
        return false;//说明不相同
     }
     if(p == null && q == null){//两个节点同时为空
        return true;//说明相同
     }
     if(p.val != q.val){//节点值不相等
        return false;//说明不相同
     }else{
     //接着判断左子树和右子树是否相同
        return isSameTree(p.left,q.left) == true && isSameTree(p.right,q.right) == true;
     }
    }
     */

    /**
     * 时间复杂度：O(m*n)
     * @param root
     * @param subRoot
     * @return
     * 判断subRoot是否为root的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null){//防止空指针异常
            return false;
        }
        if(subRoot == null){//如果subRoot为null,那么它就是任何一棵树的子树
            return true;
        }
        if(isSameTree(root,subRoot)){//如果是子树，有可能是两棵相同的树
            return true;
        }
        //继续和左子树和右子树比较，只要其中有一棵和subRoot相等就返回true
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
    */

    /**
     *
     //最坏情况下每个节点都要求高度
     public boolean isBalanced(TreeNode root) {
     if(root == null){
       return true;
     }
       return maxDepth(root) >= 0;
     }

     public int maxDepth(TreeNode root) {
     if (root == null){
     return 0;
     }
     int leftHeight = maxDepth(root.left);
     if(leftHeight < 0){
     return -1;
     }
     int rightHeight = maxDepth(root.right);
     if(rightHeight < 0){
     return -1;
     }
     if(leftHeight >= 0 && rightHeight >= 0
     && Math.abs(leftHeight-rightHeight) <= 1){//只有在这种情况下，返回真实高度
     return Math.max(leftHeight,rightHeight)+1;
     }else{
     return -1;
     }


     }
     */

    /**
     * 层序遍历
     public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> list = new ArrayList<>();
       if (root == null){
          return list;
       }
       Queue<TreeNode> queue = new LinkedList<>();
       queue.offer(root);
       while(!queue.isEmpty()){//队列为空，退出循环
         int size = queue.size();
         List<Integer> newList = new ArrayList<>();
         while(size != 0){//用于遍历当前层节点的个数
            TreeNode tmp = queue.poll();
            newList.add(tmp.val);
            size--;
            if (tmp.left != null){
            queue.offer(tmp.left);
            }
            if (tmp.right != null){
            queue.offer(tmp.right);
            }

         }
       list.add(newList);

     }
     return list;

     }
     */
}
